1. Technical Field
The present disclosure relates to decompression of data streams and, more specifically, to a method and apparatus for concurrent and stateful decompression of multiple compressed data streams.
2. Discussion of Related Art
Network security is a critical aspect of information technology. Malicious attacks such as distributed denial of service attacks may bring down even the largest of network servers. Other forms of intrusion may compromise the security of sensitive data. As modern enterprises are heavily reliant upon network service and sensitive data, even relatively minor attacks could lead to millions of dollars in damages or lost sales. More severe attacks could disrupt the critical function of an enterprise and cause immeasurable damage.
Packet inspection systems and other security measures have been developed to protect against malicious attack and other network risks. Many of these systems stand between the protected servers and the greater network and inspect incoming data packets. Packets deemed safe are allowed to proceed while suspicious packets are blocked. When used in connection with large network servers, packet inspection systems must be able to process large amounts of data quickly enough to avoid hindering communication with the protected servers.
Traditionally, these packet inspection systems were based on general-purpose central processing units (CPUs) that executed software for providing the necessary protective measures. However, to meet the demands of modern network traffic, hardware accelerators have been used to offload many processing steps that were traditionally handled by the CPU.
Network traffic consists of data streams that embody compressed data or content that is divided into a plurality of packets. Because network traffic is compressed, packet inspection devices may decompress the data streams prior to analysis. Various methods for compression and decompression are well known in the art. One popular algorithm for compression is the “Deflate” algorithm. The complementary decompression algorithm is the “Inflate” algorithm. These algorithms are based on a derivative of the Lempel-Ziv 1977 (aka LZ77) algorithm.
Compression algorithms generally transform an input data stream into a set of tokens known as “literals” and “references.” Literals are the data itself, while references refer to a previously encountered string in the input. Literals and reference tokens can be further compressed by optionally encoding them, for instance through static or dynamic Huffman encoding schemes. To remain efficient, references distances may be limited so that the entire data stream does not need to be retained to make sense of the reference tokens. This distance may be, for example, 32 Kbytes. Hence the compressed stream includes the token stream and the optional associated dynamic Huffman table(s).
Decompression works in reverse by taking a compressed input stream, extracting the variable length tokens, optionally decoding them through the lookup table (e.g. Huffman table) and presenting the decoded data to a copy engine that either copies the literal from the token or copies the data reference from the recent history of the output buffer. Increasingly these algorithms are implemented in hardware accelerator engines and are being integrated onto chip cores. Dependent on the available chip area, often only a few engines can be accommodated.
Common to these systems is that an engine needs to be dedicated to a particular data stream and process the stream in its entirety before the engine can be used to process a different stream. Hence conventional approaches are suited for situations where the entire compressed data stream is available at once.
In modern enterprise systems, data is transferred over many client/server connections (e.g. TCP connections) and the number of open connections can be substantially larger than the number of available decompression engines. In addition, connections are inherently packet oriented (TCP) and packets for different connections will arrive interspersed.
Moreover, it is increasingly common for network traffic to include compressed data. For example in compressed HTTP, all data is compressed and it is expected that up to 30% of network traffic can fall into this class.
In order to apply decompression hardware, all packets for a compressed file or message must be received and presented at once to the engine. For modern enterprise applications, there may be thousands of open connections that might carry compressed data to the servers. For packet inspection systems, like intrusion prevention systems, the number of open connections routed through the packet inspection system can be in the order of millions. The requirement to have the entire compressed data stream available can hence create significant memory pressure on the system and could therefore be exploited in service attacks. Alternatively, a decompression engine can be dedicated to a particular stream from the first to the last packet of a compressed message and thus packets could be decompressed one after the other. However, due to network traffic delays, packets belonging to a compressed message might arrive in a sequence of bursts, as determined by the network protocol (e.g. TCP/IP), and incoming packets of a single data stream may arrive over the course of several seconds or longer. Hence the number of concurrent connections that can be handled at a time is limited to the number of decompression engines. In addition, this could be exploited by attacks by not sending all packets.
In systems such as intrusion prevention systems, decompressed content must be inspected on a per packet level in order to determine intrusions as early as possible and either reject or forward the packet based on that analysis. In such a scenario, and using conventional technology, a single decompression engine must be dedicated to a single compressed data stream. The only other currently available option is to perform the decompression entirely in software.